#pragma once
template<class K,class V>
struct AVLTreeNode
{
	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf;
	AVLTreeNode(const pair<K,V>& kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
	{}
};

template<class K,class V>
struct AVLTree
{
	typedef  AVLTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		//寻找插入位置，左边小，右边大
		while (cur)
		{
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		////1、更新平衡因子
		while (parent)  //parent为空，更新到根
		{
			//新增在右，parent->bf++
			//新增在左，parent->bf--
			//
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}
			
			//1、parent->_bf ==0 之前parent->_bf==-1 parent->_bf==1
			//说明之前parent一边高一边低，这次插入填上矮的那边，parent所在子树高度不变，不需要继续往上更新
			//
			//2、parent->_bf ==  或-1  说明之前parent->_bf ==0，两边一样高，现在插入一边更高了
			//parent所在子树高度变化，需要向上更新
			//
			//3、parent->_bf == 2或-2 说明之前parent->_bf ==1或者-1，插入后失去平衡违反规则
			//就地处理---旋转


			//旋转：
			//1、让子数左右高度差不超过1
			//2、旋转过程中保持他是搜索树
			//3、更新调整孩子节点的平衡因子
			//4、让子树的高度更插入前保持一致 
			if (parent->_bf == 0)
			{
				break;
			}
			else if(parent->_bf==1 || parent->_bf ==-1)
			{ 
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//旋转
				if (parent->_bf == 2 && cur->_bf == 1)  //左旋转,右边高
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == -1) //右单旋
				{
					RotateR(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1) //左右双旋
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1) //左右双旋
				{
					RotateRL(parent);
				}
				else
				{
					assert(false);
				}
				break;
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}

	void RotateL(Node* parent)
	{
		Node* ppnode = parent->_parent; //parent的父节点

		Node* subR = parent->_right;     //需要改变的右子树
		Node* subRL = subR->_left;       //挪到parent右子树

		parent->_right = subRL;           //链接
		if (subRL)
			subRL->_parent = parent;      

		subR->_left = parent;
		parent->_parent = subR;
		if (ppnode == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			//之前的parent是上一个parent的左边还是右边
			if (ppnode->_left == parent)
			{
				ppnode->_left = subR;
			}
			else
			{
				ppnode->_right = subR;
			}
			subR->_parent = ppnode;
		}
		parent->_bf = subR->_bf = 0;
	}
	//右单旋是把parent->left的右子树，插入到parent的左子树上
	void RotateR(Node* parent)
	{
		//首先需要找到父亲的父节点
		Node* ppNode = parent->_parent;
		//找到新的父节点以及他的右子树
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		//开始改变节点的关系
		//1、将subL->_right放到parent的左边
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		//2、将subL的右节点给到parent
		//parent的父节点指向subL
		subL->_right = parent;
		parent->_parent = subL;
		//控制subL的新的父节点
		//if(root = parent)
		if (ppNode == nullptr)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
		//更改bf 高度因为
		parent->_bf = subL->_bf = 0;
	}
	void RotateLR(Node* parent)
	{
		//这里需要注意旋转因子的改变
		//应该首先把旋转因子记录下来
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;
		RotateL(parent->_left);
		RotateR(parent);
		//这儿需要对旋转因子进行单独的判断
		if (bf == -1) //说明是在subLR的左边新增的节点
		{					//subLR的左边给了subL的右边  subLR的右边给了parent的左边
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 1) //在subLR的右边新增加的节点
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else if (bf == 0)  //本身就是增加的节点
		{
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	void RotateRL(Node* parent) //右左双旋
	{
		Node* subR = parent->_right;
		Node* subRL= subR->_left;
		int bf = subRL->_bf;
		RotateR(parent->_right);
		RotateL(parent);
		//这儿需要对旋转因子进行单独的判断
		if (bf == -1) //说明是在subRL的左边新增的节点
		{					//subRL的左边给了parent的右边  subLR的右边给了subR的左边
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if (bf == 1) //在subLR的右边新增加的节点
		{
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 0)  //本身就是增加的节点
		{
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	//中序遍历
	void Inorder()
	{
		_Inorder(_root);
	}
	void _Inorder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Inorder(root->_left);
		cout << root->_kv.first <<" : "<<root->_kv.second << endl;
		_Inorder(root->_right);
	}
	bool _isBalance()
	{
		return isBalance(_root);
	}
	bool isBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);
		
		if (rightHeight - leftHeight != root->_bf)
		{
			cout << "_bf error:" << root->_kv.first<<endl;
			return false;
		}
		return abs(leftHeight - rightHeight) < 2
				&& isBalance(root->_left)
				&& isBalance(root->_right);
	}

	int Height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		int lh = Height(root->_left);
		int rh = Height(root->_right);

		return lh > rh ? lh + 1 : rh + 1;
	}


private:
	Node* _root=nullptr;
};


//void TestAVLTree()
//{
//	//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
//	//int a[] = { 16,3,7,11,9,26,18,14,15 };
//	int a[] = { 4,2,6,1,3,5,15,7,16,14 };
//	AVLTree<int,int> t;
//	for (auto& e : a)
//	{
//		t.Insert(make_pair(e,e));
//	}
//	t.Inorder();
//	cout << t._isBalance() << endl;
//
//}
#include<time.h>
void TestAVLTree()
{
	//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	//int a[] = { 16,3,7,11,9,26,18,14,15 };
	//int a[] = { 4,2,6,1,3,5,15,7,16,14 };
	srand(time(0));
	const size_t N = 100;
	AVLTree<int, int> t;
	for (size_t i = 0; i < N; ++i)
	{
		size_t x = rand();
		t.Insert(make_pair(x, x));
	}

	t.Inorder();
	cout << t._isBalance() << endl;

}

